#include<iostream>
using namespace std;
#include<math.h>

//剑指offer题7：现在要求输入一个整数n，请求出斐波那契数列的第n项。（通项公式: f(n) = f(n-1) + f(n-2)）注意，f(0) = 0
////    思路一：迭代循环法    
//		思路二：公式法    
//		思路三：尾递归法(当递归调用是整个函数体中最后执行的语句，且它的返回值不属于表达式的一部分时，这个递归就是为递归)
int Fibonacci(size_t n)//循环迭代法  //0 1 1 2 3 5 8 13 21...
{
	if (n < 1)return n;
	int tmp, acc1 = 0, acc2 = 1;
	while (--n)
	{
		tmp = acc2;
		acc2 += acc1;
		acc1 = tmp;
	}
	return acc2;
}
int Fibonacci2(size_t n)//公式法
{
	double x = pow((1 + sqrt(5)) / 2, n);
	double y = pow((1 - sqrt(5)) / 2, n);
	return 1 / sqrt(5) * (x - y);
}
int Fibonacci3(int n, int acc1 = 0, int acc2 = 1)//尾递归法
{
	if (n == 0)return 0;
	if (n == 1)
	return acc2;
	else
	return Fibonacci3(n - 1, acc2, acc1 + acc2);
}
void test_offer7()
{
	cout << Fibonacci(5) << endl;
	cout << Fibonacci2(5) << endl;
	cout << Fibonacci3(5) << endl;
}

//剑指offer题8：一只青蛙一次可以跳上1级台阶，也可以跳上2阶台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。
//         分析:如果想跳一次就跳上第n级台阶，那么青蛙上一次一定在第n-1或n-2级台阶上；f(n) = f(n-1) + f(n-2)  注意f(0) = 1
int FlogJumpStep(size_t n)// 0 1 2 3 5 8 13 21...
{
	if (n < 2)return n;
	int acc0 = 0, acc1 = 1;
	int tmp;
	while (--n)
	{
		tmp = acc1;
		acc1 += acc0;
		acc0 = tmp;
	}
	return acc1;
}

//剑指offer题9：一只青蛙一次可以跳上1级台阶，也可以跳上2阶台阶...也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
//    如上分析得：f(n) = f(n-1)+f(n-2)+...+f(1);  注意f(0) = 1
//                f(n-1) = f(n-2)+f(n-3)+...+f(1);     ----->   f(n) = 2 * f(n-1)
int FlogJumpStep2(size_t n)
{
	if (n < 1)return n;
	int acc2, acc1 = 1;
	while (--n)
	{
		acc2 = acc1 * 2;
		acc1 = acc2;
	}
	return acc1;
}

//剑指offer题10：我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
//               请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法
int RectanglePave(size_t n)//0 1 2 3 5 8 13 21...
{
	if (n < 2)return n;
	int acc0 = 0, acc1 = 1;
	int tmp;
	while (--n)
	{
		tmp = acc1;
		acc1 += acc0;
		acc0 = tmp;
	}
	return acc1;
}

int main()
{
	int n = 5;
	cout << "test_offer7   " << Fibonacci(n) << endl;//7
	cout << "test_offer7   " << Fibonacci2(n) << endl;//7
	cout << "test_offer7   " << Fibonacci3(n) << endl;//7
	cout << "test_offer8   " << FlogJumpStep(n) << endl;//8
	cout << "test_offer9   " << FlogJumpStep2(n) << endl;//9
	cout << "test_offer10  " << RectanglePave(n) << endl;//10
	
	return 0;
}
